package member_niejia;

import algorithms.SortAlgorithm;

public class QuickSort3Way implements SortAlgorithm {
    @Override
    public void sort(int[] arr) {
        quickSort3Way(arr, 0, arr.length - 1);
    }

    private void quickSort3Way(int[] arr, int low, int high) {
        if (high <= low) return;

        int lt = low, gt = high;
        int pivot = arr[low];
        int i = low + 1;

        while (i <= gt) {
            if (arr[i] < pivot) {
                swap(arr, lt++, i++);
            } else if (arr[i] > pivot) {
                swap(arr, i, gt--);
            } else {
                i++;
            }
        }

        quickSort3Way(arr, low, lt - 1);
        quickSort3Way(arr, gt + 1, high);
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    @Override
    public String getDeveloperName() {
        return "聂嘉";
    }

    @Override
    public String getAlgorithmName() {
        return "QuickSort3Way";
    }
}